home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2E.ASM < prev    next >
Assembly Source File  |  1990-01-17  |  9KB  |  207 lines
  1. ;
  2. ; This program originally available on the Motorola DSP bulletin board.
  3. ; It is provided under a DISCLAMER OF WARRANTY available from
  4. ; Motorola DSP Operation, 6501 Wm. Cannon Drive W., Austin, Tx., 78735.
  5. ; 
  6. ; 1024-Point, 3.39ms Non-In-Place FFT. 
  7. ; 
  8. ; Last Update 04 Feb 87   Version 1.0
  9. ;
  10. fftr2e  macro   data,coef
  11. fftr2e  ident   1,0
  12. ;
  13. ; 1024 Point Complex Fast Fourier Transform Routine
  14. ;
  15. ; This routine performs a 1024 point complex FFT on external data
  16. ; using the Radix 2, Decimation in Time, Cooley-Tukey FFT algorithm.
  17. ;
  18. ;    Complex input and output data
  19. ;        Real data in X memory
  20. ;        Imaginary data in Y memory
  21. ;    Normally ordered input data
  22. ;    Bit reversed output data
  23. ;       Coefficient lookup table
  24. ;        -Cosine values in X memory
  25. ;        -Sine values in Y memory
  26. ;
  27. ; Macro Call - fftr2e   data,coef
  28. ;
  29. ;       data       start of external data buffer
  30. ;       coef       start of sine/cosine table
  31. ;
  32. ; Radix 2, Decimation In Time Cooley-Tukey FFT algorithm
  33. ;             ___________
  34. ;            |           | 
  35. ; ar,ai ---->|  Radix 2  |----> ar',ai'
  36. ; br,bi ---->| Butterfly |----> br',bi'
  37. ;            |___________|
  38. ;                  ^
  39. ;                  |
  40. ;                wr,wi
  41. ;
  42. ;       ar' = ar + wr*br - wi*bi
  43. ;       ai' = ai + wi*br + wr*bi
  44. ;       br' = ar - wr*br + wi*bi = 2*ar - ar'
  45. ;       bi' = ai - wi*br - wr*bi = 2*ai - ai'
  46. ;
  47. ; Address pointers are organized as follows:
  48. ;
  49. ;  r0 = ar,ai input pointer     n0 = group offset       m0 = modulo (points)
  50. ;  r1 = br,bi input pointer     n1 = group offset       m1 = modulo (points)
  51. ;  r2 = ext. data base address  n2 = groups per pass    m2 = 256 pt fft counter
  52. ;  r3 = coef. offset each pass  n3 = coefficient base addr.     m3 = linear
  53. ;  r4 = ar',ai' output pointer  n4 = group offset       m4 = modulo (points)
  54. ;  r5 = br',bi' output pointer  n5 = group offset       m5 = modulo (points)
  55. ;  r6 = wr,wi input pointer     n6 = coef. offset       m6 = bit reversed
  56. ;  r7 = not used (*)            n7 = not used (*)       m7 = not used (*)
  57. ;
  58. ;       * - r7, n7 and m7 are typically reserved for a user stack pointer.
  59. ;
  60. ; Alters Data ALU Registers
  61. ;       x1      x0      y1      y0
  62. ;       a2      a1      a0      a
  63. ;       b2      b1      b0      b
  64. ;
  65. ; Alters Address Registers
  66. ;       r0      n0      m0
  67. ;       r1      n1      m1
  68. ;       r2      n2      m2
  69. ;       r3      n3      m3
  70. ;       r4      n4      m4
  71. ;       r5      n5      m5
  72. ;       r6      n6      m6
  73. ;
  74. ; Alters Program Control Registers
  75. ;       pc      sr
  76. ;
  77. ; Uses 8 locations on System Stack                                           
  78. ;
  79. ; Latest Revision - 4-Feb-87
  80. ;
  81. _points equ     1024            ;number of FFT points
  82. _intdata        equ     0       ;address of internal data workspace
  83.         move    #data,r2        ;initialize input pointers
  84.         move    r2,r0
  85.         move    #_points/4,n0   ;initialize butterflies per group
  86.         move    n0,n4           ;initialize pointer offsets
  87.         move    n0,n6           ;initialize coefficient offset
  88.         move    #coef,n3        ;initialize coefficient base address
  89.         move    #_points-1,m0   ;initialize address modifiers
  90.         move    m0,m1           ;for modulo(points) addressing
  91.         move    m0,m4
  92.         move    m0,m5
  93.         move    #-1,m3          ;linear addressing for coefficient base offset
  94.         move    #0,m2           ;initialize 256 point fft counter
  95.         move    m2,m6           ;initialize coefficient address modifier
  96.                                 ;for reverse carry (bit reversed) addressing
  97. ;
  98. ; Do first and second Radix 2 FFT passes
  99. ;
  100.         move            x:(r0)+n0,x0
  101.         tfr     x0,a    x:(r0)+n0,y1
  102.  
  103.         do      n0,_twopass
  104.         tfr     y1,b    x:(r0)+n0,y0
  105.         add     y0,a    x:(r0),x1                       ;ar+cr
  106.         add     x1,b    r0,r4                           ;br+dr
  107.         add     a,b     (r0)+n0                         ;ar'=(ar+cr)+(br+dr)
  108.         subl    b,a     b,x:(r0)+n0                     ;br'=(ar+cr)-(br+dr)
  109.         tfr     x0,a    a,x0            y:(r0),b
  110.         sub     y0,a                    y:(r4)+n4,y0    ;ar-cr
  111.         sub     y0,b    x0,x:(r0)                       ;bi-di
  112.         add     a,b                     y:(r0)+n0,x0    ;cr'=(ar-cr)+(bi-di)
  113.         subl    b,a     b,x:(r0)                        ;dr'=(ar-cr)-(bi-di)
  114.         tfr     x0,a    a,x0            y:(r4),b
  115.         add     y0,a                    y:(r0)+n0,y0    ;bi+di
  116.         add     y0,b    x0,x:(r0)+n0                    ;ai+ci
  117.         add     b,a                     y:(r0)+,x0      ;ai'=(ai+ci)+(bi+di)
  118.         subl    a,b                     a,y:(r4)+n4     ;bi'=(ai+ci)-(bi+di)
  119.         tfr     x0,a                    b,y:(r4)+n4
  120.         sub     y0,a    x1,b                            ;ai-ci
  121.         sub     y1,b    x:(r0)+n0,x0                    ;dr-br
  122.         add     a,b     x:(r0)+n0,y1                    ;ci'=(ai-ci)+(dr-br)
  123.         subl    b,a                     b,y:(r4)+n4     ;di'=(ai-ci)-(dr-br)
  124.         tfr     x0,a                    a,y:(r4)+
  125. _twopass
  126. ;                                                                   
  127. ; Do remaining 8 FFT passes as four 256 point Radix 2 FFT's using internal data
  128. ; and external coefficients.
  129. ;
  130. ; Each 256 point Radix 2 FFT consists of 8 passes.  The first pass uses external
  131. ; input data and internal output data to move the data on-chip.  Intermediate
  132. ; passes use internal input data and internal output data to keep the data
  133. ; on-chip.  The last pass uses internal input data and external output data
  134. ; to move the data off-chip.
  135. ;
  136.         do      #4,_end_fft     ;do 256 point fft four times
  137.         move    r2,r0           ;get external data input address for first pass
  138.         move    m2,r3           ;update coefficient offset
  139.         move    #256/2,n0       ;initialize butterflies per group
  140.         move    #1,n2           ;initialize groups per pass
  141.  
  142.         do      #7,_end_pass    ;do first 7 passes out of 8
  143.         move    #_intdata,r4    ;initialize A output pointer
  144.         move    n0,n1           ;initialize pointer offsets
  145.         move    n0,n4
  146.         move    n0,n5
  147.         lua     (r0)+n0,r1      ;initialize B input pointer
  148.         lua     (r4)+n4,r5      ;initialize B output pointer
  149.         lua     (r3)+n3,r6      ;initialize W input pointer
  150.         move    (r5)-
  151.  
  152.         do      n2,_end_grp
  153.         move    x:(r1),x1       y:(r6),y0       ;lookup -sine value
  154.         move    x:(r5),a        y:(r0),b
  155.         move    x:(r6)+n6,x0            ;lookup -cosine value
  156.  
  157.                                                  
  158.         do      n0,_end_bfy     ;Radix 2 DIT butterfly kernel with constant
  159.         mac     x1,y0,b                         y:(r1)+,y1   ;twiddle factor
  160.         macr    -x0,y1,b        a,x:(r5)+       y:(r0),a
  161.         subl    b,a             x:(r0),b        b,y:(r4)
  162.         mac     -x1,x0,b        x:(r0)+,a       a,y:(r5)
  163.         macr    -y1,y0,b        x:(r1),x1
  164.         subl    b,a             b,x:(r4)+       y:(r0),b
  165. _end_bfy
  166.         move    a,x:(r5)+n5     y:(r1)+n1,y1    ;dummy load of x1 and y1
  167.         move    x:(r0)+n0,x1    y:(r4)+n4,y1
  168. _end_grp
  169.         move    n0,b1
  170.         lsr     b       n2,a1   ;divide butterflies per group by two
  171.         lsl     a       b1,n0   ;multiply groups per pass by two
  172.         move            r3,b1
  173.         lsr     b       a1,n2   ;divide coefficient offset by two
  174.         move            b1,r3
  175.         move            #_intdata,r0    ;intermediate passes use internal input data
  176. _end_pass
  177. ;        
  178. ; Do last FFT pass and move output data off-chip to external data memory.
  179. ;
  180.         move    n1,n0           ;correct pointer offset for last pass
  181.         move    r2,r4           ;initialize A output pointer
  182.         lua     (r0)+,r1        ;initialize B input pointer
  183.         lua     (r4)-n4,r5      ;initialize B output pointer
  184.         lua     (r3)+n3,r6      ;initialize W input pointer
  185.         move    (r5)+
  186.         move    x:(r1),x1       y:(r6),y0
  187.